package org.example.algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinimumTotalSolution {
    public static void main(String[] args) {
        MinimumTotalSolution solution = new MinimumTotalSolution();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(-1);
        List<Integer> list2 = new ArrayList<>();
        list2.add(-2);
        list2.add(-3);
//        List<Integer> list3 = new ArrayList<>();
//        list3.add(6);
//        list3.add(5);
//        list3.add(7);
//        List<Integer> list4 = new ArrayList<>();
//        list4.add(4);
//        list4.add(1);
//        list4.add(8);
//        list4.add(3);
        list.add(list1);
        list.add(list2);
//        list.add(list3);
//        list.add(list4);
        int res = solution.minimumTotal2(list);
        System.out.println(res);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int[][] dp = new int[row][row];
        dp[0][0] = triangle.get(0).get(0);

        for (int i=1;i<row;i++) {
            for (int j=0;j<i+1;j++) {
                if (j-1 < 0) {
                    dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
                } else if (j>i-1) {
                    dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
                }
            }
        }
        int res = dp[row-1][0];
        for (int j=1;j<row;j++) {
            res = Math.min(res, dp[row-1][j]);
        }
        return res;
    }

    public int minimumTotal2(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] mem = new int[size][size];
        for (int i=0;i<size;i++) {
            Arrays.fill(mem[i], Integer.MAX_VALUE);
        }
        mem[0][0] = triangle.get(0).get(0);
        for (int i=0;i<size;i++) {
            dfs(triangle, size-1, i, mem);
        }
        int res = mem[size-1][0];
        for (int i=1;i<size;i++) {
            res = Math.min(res, mem[size-1][i]);
        }
        return res;
    }

    private int dfs(List<List<Integer>> triangle, int i, int j, int[][] mem) {
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        if (mem[i][j] != Integer.MAX_VALUE) {
            return mem[i][j];
        }
        if (j==0) {
            return mem[i][j] = dfs(triangle, i-1, j, mem) + triangle.get(i).get(j);
        }
        if (j == i) {
            return mem[i][j] = dfs(triangle, i-1, j-1, mem) + triangle.get(i).get(j);
        }
        return mem[i][j] = Math.min(dfs(triangle, i-1, j, mem), dfs(triangle, i-1, j-1, mem)) + triangle.get(i).get(j);
    }
}
